\chapter{C\'alculo de autovalores}

Una forma directa de calcular los autovalores de una matriz es obtener 
las ra\'ices del polinomio caracter\'istico 
$P(\lambda)=det(A-\lambda I)$ y luego calcular los vectores 
caracter\'isticos (autovectores) resolviendo el sistema lineal 
asociado a cada autovalor. 
Claramente para matrices grandes es dif\'icil obtener $P(\lambda)$, 
a\'un si se lo consiguiera no es f\'acil calcular todas las ra\'ices 
de cualquier polinomio de n-\'esimo grado. 
Es por eso que los m\'etodos de aproximaci\'on se presentan como una 
buena opci\'on para estas situaciones.

%~ \section{Teorema de los c\'irculos de Gerschgorin}
%~ \begin{theorem}
	%~ Si $A\in\mathbb{C}^{n\times n}$, entonces cada autovalor de $A$ 
	%~ est\'a contenido en alg\'un disco $D_i$, donde $D_i$ tiene centro 
	%~ en $a_{ii}$ y radio $\sum_{j\neq i} |a_{ij}|$. M\'as a\'un, si la 
	%~ uni\'on de $k$ discos es disjunta de la uni\'on de los otros $n-k$, 
	%~ contienen $k$ y $n-k$ autovalores respectivamente (y en particular, 
	%~ un disco disjunto a los dem\'as contiene exactamente un autovalor).
%~ \end{theorem}

\section{M\'etodo de la potencia}

Este m\'etodo sirve para calcular el autovalor de mayor m\'odulo de 
$A \in \real^{n\times n}$, $\lambda_1$ junto con un autovector 
asociado.
Requiere que $\lambda_{1}$ sea simple (tenga multiplicidad uno), y que 
exista una base de $R^n$ formada por autovectores de $A$.

Los autovectores forman una base ${v_1,\ldots,v_n}$ (donde $v_i$ es el
 autovector asociado a $\lambda_i$), entonces existen constantes
$\beta_1,\ldots,\beta_n$ tal que para todo $x$ se cumple 
$\displaystyle x = \sum_{i=1}^n \beta_i v_i$. 

\par
Multiplicando a izquierda por $A^k$ se obtiene 
$\displaystyle A^kx = \sum_{i=1}^n \beta_i A^k v_i = 
\sum_{i=1}^n \beta_i \lambda_i^k v_i$. 

\par
Sacando factor com\'un $\lambda_1^k$, 
$\displaystyle A^kx = \lambda_1^k \sum_{i=1}^n \beta_i 
\left(\frac{\lambda_i}{\lambda_1}\right)^k v_i = 
\lambda_i^k \left(\beta_1 v_1 + \sum_{i=2}^n \beta_i 
\left(\frac{\lambda_i}{\lambda_1}\right)^k v_i \right).$

\par
Como $|\lambda_1| > |\lambda_i| \; \forall i > 1$, 
$\displaystyle \frac{\lambda_i}{\lambda_1} < 1 \rightarrow 
\lim_{k\to\infty} \left(\frac{\lambda_i}{\lambda_1}\right)^k = 0,$ 

\par
entonces vale que
$\displaystyle \lim_{k\to\infty} A^k x = 
\lim_{k\to\infty} \lambda_1^k \sum_{i=1}^n \beta_i 
\left(\frac{\lambda_j}{\lambda_1}\right)^k v_i 
= \lim_{k\to\infty} \lambda_1^k \beta_1 v_1 $.

\paragraph{}
Se define la sucesi\'on $\displaystyle x_{k}=A^{k}x = 
\lambda_{1}^{k}(\beta_{1}v_{1}+\varepsilon_{k})$, 
donde $\displaystyle \varepsilon_{k} = \sum_{i=2}^n \beta_i 
\left(\frac{\lambda_i}{\lambda_1}\right)^k v_i$ con 
$\displaystyle \lim_{k\to\infty} \varepsilon_{k} = 0$. \\
Esta sucesi\'on tiende a cero o diverge dependiendo del valor de 
$\lambda_{1}$, por lo cual se normaliza la 
sucesi\'on, aplicando una funci\'on conveniente con el fin de lograr 
que tienda a $\lambda_{1}$.

\paragraph{}
Se define entonces la funci\'on cont\'inua 
$\Phi: \real^{n} \mapsto \real$, de forma tal que 
$\Phi(\alpha x) = \alpha\Phi(x)$ y $\Phi(x) \neq 0 \; 
\forall \; x \neq 0$.
$\displaystyle \mu_k = \frac{\Phi(x_{k+1})}{\Phi(x_{k})} = 
\displaystyle \lambda_{1}\frac{\Phi(\beta_{1}v_{1}+\varepsilon_{k+1})}
{\Phi(\beta_{1}v_{1}+\varepsilon_{k})}.$
$\displaystyle \lim_{k\to\infty} \lambda_{1}
\frac{\Phi(\beta_{1}v_{1}+\varepsilon_{k+1})}
{\Phi(\beta_{1}v_{1}+\varepsilon_{k})} = 1$ 
porque $\displaystyle \lim_{k\to\infty} \varepsilon_{k} = 0$, entonces 
$\displaystyle \lim_{k\to\infty} \mu_k = 
\lambda_{1}\frac{\Phi(\beta_{1}v_{1})}{\Phi(\beta_{1}v_{1})}$

\par
Si $\displaystyle \Phi(\beta_{1}v_{1}) \neq 0$, 
$\displaystyle \lim_{k\to\infty} \mu_k = \lambda_{1}$.

\par
En el paso $i+1$, $\Phi(y)=x_i^ty$.
El m\'etodo de las potencias para obtener el autovalor $\lambda_{1}$ 
dado $x_i$ resulta
$$x_{i+1} = \frac{Ax}{||Ax||} \textrm{ y } \mu_{i+1} = \frac{x_i^t x_{i+1}}{x_i^t x_i}.$$

\begin{remark}
	Si $x$ es ortogonal a $v_1$ entonces $\beta_1=0$, debiendo 
	elegirse otro valor de $x$.
\end{remark}

\begin{remark}
	La velocidad de convergencia para este m\'etodo depende de la 
	velocidad con la cual $\varepsilon_{k}$ tiende a cero, que a su 
	vez depende de cu\'an chico sea el cociente 
	$\displaystyle \frac{\lambda_{2}}{\lambda_{1}}$, es decir de 
	cu\'an alejado est\'a el autovalor de mayor m\'odulo del siguiente 
	(en m\'odulo), y en consecuencia del resto de los autovalores. 
\end{remark}

\paragraph{}
Una desventaja de este m\'etodo es que al inicio no se sabe si la 
matriz tiene o no un \'unico autovalor dominante. 
Tampoco es f\'acil seleccionar $x_0$ para asegurar que no sea ortogonal 
al autovector asociado al autovalor dominante.

El m\'etodo es aplicable, por ejemplo, en matrices sim\'etricas con 
todos sus elementos positivos. 
El teorema espectral afirma que existe una base de autovectores 
(ortogonal), mientras que el teorema de Perron-Frobenius garantiza 
que $\lambda_1$ es simple (y que todas las componentes de su autovector 
tienen el mismo signo).

\section{M\'etodo inverso de la potencia}

Esta variaci\'on del m\'etodo de la potencia sirve para calcular el 
autovalor m\'as cercano a un cierto valor $\mu$ 
(por ejemplo $\lambda_k$), y un autovector asociado.
Si $\mu \neq \lambda_k$ entonces existe $(A - \mu I)^{-1}$ y su 
autovalor de mayor m\'odulo es $(\lambda_k-\mu)^{-1}$, lo cual permite 
calcular $\lambda_k$ utilizando el m\'etodo de la potencia sobre 
$A - \mu I$.

\paragraph{}
Existe una variante, denominada iteraci\'on del cociente de Rayleigh, 
que consiste en aprovechar en el paso $i$-\'esimo la aproximaci\'on 
$\mu_i$, multiplicando por $A-\mu_i I$ en vez de $A-\mu I$.
